import java.util.LinkedList;

public class MyStack {
    //利用队列实现栈
    LinkedList<Integer> queue1;
    LinkedList<Integer> queue2;
    public MyStack() {
         queue1 = new LinkedList<>();
         queue2 = new LinkedList<>();
    }

    public void push(int x) {
          //哪个队列不为空，就放进哪个队列
          if(queue1.isEmpty()) {
              queue2.offer(x);
          }
          if(queue2.isEmpty()) {
              queue1.offer(x);
          }
    }

    public int pop() {
        if(empty()) {
            return -1;
        }
        //两个队列中一定会有一个为空
        int val = 0;
        if(queue1.isEmpty()) {
            //将queue2的元素全部入队到queue1中，然后删除queue1中的最后一个元素
            while(!queue2.isEmpty()) {
                queue1.offer(queue2.poll());
            }

            val = queue1.get(queue1.size() - 1);
            queue1.remove(queue1.size() - 1);
            return val;
        }

        if(queue2.isEmpty()) {
            //将queue1中的元素全部入队到
            while(!queue1.isEmpty()) {
                queue2.offer(queue1.poll());
            }

            val = queue2.get(queue2.size() - 1);
            queue2.remove(queue2.size() - 1);
            return val;
        }

        return val;
    }

    public int top() {
        //两个队列中一定会有一个为空
        if(empty()) {
            return -1;
        }
        int val = 0;
        if(queue1.isEmpty()) {
            //将queue2的元素全部入队到queue1中，然后删除queue1中的最后一个元素
            while(!queue2.isEmpty()) {
                queue1.offer(queue2.poll());
            }

            val = queue1.get(queue1.size() - 1);
        }

        if(queue2.isEmpty()) {
            //将queue1中的元素全部入队到
            while(!queue1.isEmpty()) {
                queue2.offer(queue1.poll());
            }

            val = queue2.get(queue2.size() - 1);
        }

        return val;
    }

    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}
